package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author shengxiao
 * @date 2021/7/21 16:04
 * 基数排序【桶排序的进阶】
 */
//  radix：基数
public class RadixSort {

    public static void main(String[] args) {
//        int[] arr = {53, 3, 542, 748, 14, 214} ;
//        radixSort(arr);

        // 创建80000个的随机的数组
        // 如果是创建一个80000000万的一个数组，则出现内存不足错误；80000000 * 10(创建10个数组作为桶) * 4(int类型占4个字节) /1024(M)/1024(G) = 3.27G（占用内存）
        // 所以，使用基数排序要时刻小心，数组创建太大易造成内存不足
        int[] arr = new int[80000000] ;
        for(int i = 0 ; i < 80000000 ; i++){
            arr[i] = (int) (Math.random() * 800000000);  // 生成一个[0,8000000)的数，为什么要取怎么大，为了避免取到相同的值
        }
//        Date date1 = new Date() ;   // 实体类
//        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String date1Str = sdf.format(date1);
//        System.out.println("排序前的时间是=" + date1Str);

        long before = System.currentTimeMillis() ;
        //System.out.println("排序前的时间是=" + System.currentTimeMillis()) ;

        radixSort(arr);

//        Date date2 = new Date() ;   // 实体类
//        String date2Str = sdf.format(date2);
//        System.out.println("排序后的时间是=" + date2Str);  // 选择排序用时4s
        long after = System.currentTimeMillis() ;

        System.out.println("执行总时间" + (after - before) / 1000.0 + "s");    // 80000数据，执行总时间0.018s
    }                                                                        // 800000数据，执行总时间0.101s
                                                                             // 8000000数据，执行总时间0.759s
                                                                             // 80000000数据，Java heap space，Java堆空间，内存不足错误


    // 基数排序方法
    public static void radixSort(int[] arr){

        // 根据前面的推导过程，我们可以得到最终的基数排序的代码

        // 1. 得到数组中最大的数的位数
        int max = arr[0] ;  // 假设第一个数字就是最大数
        for(int i = 1 ; i < arr.length ; i++){
            if(arr[i] > max){
                max = arr[i] ;
            }
        }

        // 得到最大数是几位数,这个方式蛮灵活的
        int maxLength = (max + "").length() ;



        // 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        // 说明
        // 1. 二维数组包含10个一维数组
        // 2. 为了防止在放入数的时候，数据溢出，则每个一维数组（桶），大小定为arr.length
        // 3. 明确，基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length] ;

        // 为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶每次放入的数据个数
        // 可以这样理解
        // bucketElementCounts[0]，记录的就是 bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10] ;   // 默认初始值为0

        // 这里我们使用循环将代码处理

        for(int i = 0, n = 1 ; i < maxLength ; i++, n *= 10){
            // （针对每个元素的对应的位进行排序处理），eg：第一次是个位，第二次是十位，第三次是百位
            int indexOfBucket = 0 ;
            for(int j = 0 ; j < arr.length ; j++){
                // 取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10 ;
                // 放入到对应的桶中
                // indexOfBucket：记录对于digitOfElement基数下的桶里面元素的下标
                // 对于每个基数的桶，第一次元素添加的时候，indexOfBucket有默认初始值0,且刚好此时桶中存放了一个数据
                indexOfBucket = bucketElementCounts[digitOfElement] ;
                //System.out.println(bucketElementCounts[digitOfElement]);    // 测试
                bucket[digitOfElement][indexOfBucket] = arr[j]  ;

                // 注意：下面这个指示器移动不能写成indexOfBucket++，因为indexOfBucket只是个变量，只保存了当前对应的值
                // 而下面的bucketElementCounts[digitOfElement]对应的是一块地址空间的元素，如果只是进行修改indexOfBucket变量
                // 此时是不会影响到原来的地址空间中数据的变动，即二者的变化不是 同步的，如果是引用数据类型，那么是可以按地址访问。
                bucketElementCounts[digitOfElement]++ ;   // 可能下一次继续添加到这个桶里，故指示器向前移动
                //System.out.println(bucketElementCounts[digitOfElement]);    // 测试

            }
            // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
            int index = 0 ;
            // 遍历每一个桶，并将桶中的数据，放入到原来的数组
            // bucketElementCounts.length：注意：刚开始添加了一个数据，indexOfBucket为0，bucketElementCounts.length为1
            for(int k = 0 ; k < bucketElementCounts.length ; k++){
                // 如果桶中有数据，我们才放入到原数组
                if(bucketElementCounts[k] != 0){
                    // 循环该桶即第k个桶（即第k个数组），放入
                    for(int l = 0 ; l < bucketElementCounts[k] ; l++){
                        // 取出元素放入到arr
                        arr[index++] = bucket[k][l] ;
                    }

                }
                // 第i+1轮处理后，需要将每个bucketElementCounts[k]置为0！！！
                // 因为下一趟排序后是对原来修改过的数组arr，再次按十位数基数重新存放到桶中，故要先置为0
                bucketElementCounts[k] = 0 ;    // 更准确的来讲，是当第k个桶的元素覆盖到原数组后，就将bucketElementCounts数组对应的桶的元素的存放个数清0
            }
            //System.out.println("第" + (i + 1) + "轮，对个位数的排序处理 arr = " + Arrays.toString(arr));
        }


        /*// 第一轮排序（针对每个元素的个位进行排序处理）
        int indexOfBucket = 0 ;
        for(int j = 0 ; j < arr.length ; j++){
            // 取出每个元素的个位数
            int digitOfElement = arr[j] / 1 % 10 ;
            // 放入到对应的桶中
            // indexOfBucket：记录对于digitOfElement基数下的桶里面元素的下标
            // 对于每个基数的桶，第一次元素添加的时候，indexOfBucket有默认初始值0,且刚好此时桶中存放了一个数据
            indexOfBucket = bucketElementCounts[digitOfElement] ;
            //System.out.println(bucketElementCounts[digitOfElement]);    // 测试
            bucket[digitOfElement][indexOfBucket] = arr[j]  ;

            // 注意：下面这个指示器移动不能写成indexOfBucket++，因为indexOfBucket只是个变量，只保存了当前对应的值
            // 而下面的bucketElementCounts[digitOfElement]对应的是一块地址空间的元素，如果只是进行修改indexOfBucket变量
            // 此时是不会影响到原来的地址空间中数据的变动，即二者的变化不是 同步的，如果是引用数据类型，那么是可以按地址访问。
            bucketElementCounts[digitOfElement]++ ;   // 可能下一次继续添加到这个桶里，故指示器向前移动
            //System.out.println(bucketElementCounts[digitOfElement]);    // 测试

        }
        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
        int index = 0 ;
        // 遍历每一个桶，并将桶中的数据，放入到原来的数组
        // bucketElementCounts.length：注意：刚开始添加了一个数据，indexOfBucket为0，bucketElementCounts.length为1
        for(int k = 0 ; k < bucketElementCounts.length ; k++){
            // 如果桶中有数据，我们才放入到原数组
            if(bucketElementCounts[k] != 0){
                // 循环该桶即第k个桶（即第k个数组），放入
                for(int l = 0 ; l < bucketElementCounts[k] ; l++){
                    // 取出元素放入到arr
                    arr[index++] = bucket[k][l] ;
                }

            }
            // 第一轮处理后，需要将每个bucketElementCounts[k]置为0！！！
            // 因为下一趟排序后是对原来修改过的数组arr，再次按十位数基数重新存放到桶中，故要先置为0
            bucketElementCounts[k] = 0 ;    // 更准确的来讲，是当第k个桶的元素覆盖到原数组后，就将bucketElementCounts数组对应的桶的元素的存放个数清0
        }
        System.out.println("第1轮，对个位数的排序处理 arr = " + Arrays.toString(arr));

        // 第二轮排序（针对每个元素的十位进行排序处理）
        for(int j = 0 ; j < arr.length ; j++){
            // 取出每个元素的个位数
            int digitOfElement = arr[j] / 10 % 10 ;
            // 放入到对应的桶中
            // indexOfBucket：记录对于digitOfElement基数下的桶里面元素的下标
            // 对于每个基数的桶，第一次元素添加的时候，indexOfBucket有默认初始值0,且刚好此时桶中存放了一个数据
            indexOfBucket = bucketElementCounts[digitOfElement] ;
            //System.out.println(bucketElementCounts[digitOfElement]);    // 测试
            bucket[digitOfElement][indexOfBucket] = arr[j]  ;

            // 注意：下面这个指示器移动不能写成indexOfBucket++，因为indexOfBucket只是个变量，只保存了当前对应的值
            // 而下面的bucketElementCounts[digitOfElement]对应的是一块地址空间的元素，如果只是进行修改indexOfBucket变量
            // 此时是不会影响到原来的地址空间中数据的变动，即二者的变化不是 同步的，如果是引用数据类型，那么是可以按地址访问。
            bucketElementCounts[digitOfElement]++ ;   // 可能下一次继续添加到这个桶里，故指示器向前移动
            //System.out.println(bucketElementCounts[digitOfElement]);    // 测试

        }
        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
        index = 0 ;
        // 遍历每一个桶，并将桶中的数据，放入到原来的数组
        // bucketElementCounts.length：注意：刚开始添加了一个数据，indexOfBucket为0，bucketElementCounts.length为1
        for(int k = 0 ; k < bucketElementCounts.length ; k++){
            // 如果桶中有数据，我们才放入到原数组
            if(bucketElementCounts[k] != 0){
                // 循环该桶即第k个桶（即第k个数组），放入
                for(int l = 0 ; l < bucketElementCounts[k] ; l++){
                    // 取出元素放入到arr
                    arr[index++] = bucket[k][l] ;
                }

            }
            // 第二轮处理后，需要将每个bucketElementCounts[k]置为0！！！
            // 因为下一趟排序后是对原来修改过的数组arr，再次按百位数基数重新存放到桶中，故要先置为0
            bucketElementCounts[k] = 0 ;    // 更准确的来讲，是当第k个桶的元素覆盖到原数组后，就将bucketElementCounts数组对应的桶的元素的存放个数清0
        }
        System.out.println("第2轮，对百位数的排序处理 arr = " + Arrays.toString(arr));

        // -------------------------------------------------------------------

        // 第三轮排序（针对每个元素的十位进行排序处理）
        for(int j = 0 ; j < arr.length ; j++){
            // 取出每个元素的百位数
            int digitOfElement = arr[j] / 100 % 10 ;    // 注：748 / 100 == 748 /100 % 10 == 7
            // 放入到对应的桶中
            // indexOfBucket：记录对于digitOfElement基数下的桶里面元素的下标
            // 对于每个基数的桶，第一次元素添加的时候，indexOfBucket有默认初始值0,且刚好此时桶中存放了一个数据
            indexOfBucket = bucketElementCounts[digitOfElement] ;
            //System.out.println(bucketElementCounts[digitOfElement]);    // 测试
            bucket[digitOfElement][indexOfBucket] = arr[j]  ;

            // 注意：下面这个指示器移动不能写成indexOfBucket++，因为indexOfBucket只是个变量，只保存了当前对应的值
            // 而下面的bucketElementCounts[digitOfElement]对应的是一块地址空间的元素，如果只是进行修改indexOfBucket变量
            // 此时是不会影响到原来的地址空间中数据的变动，即二者的变化不是 同步的，如果是引用数据类型，那么是可以按地址访问。
            bucketElementCounts[digitOfElement]++ ;   // 可能下一次继续添加到这个桶里，故指示器向前移动
            //System.out.println(bucketElementCounts[digitOfElement]);    // 测试

        }
        // 按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
        index = 0 ;
        // 遍历每一个桶，并将桶中的数据，放入到原来的数组
        // bucketElementCounts.length：注意：刚开始添加了一个数据，indexOfBucket为0，bucketElementCounts.length为1
        for(int k = 0 ; k < bucketElementCounts.length ; k++){
            // 如果桶中有数据，我们才放入到原数组
            if(bucketElementCounts[k] != 0){
                // 循环该桶即第k个桶（即第k个数组），放入
                for(int l = 0 ; l < bucketElementCounts[k] ; l++){
                    // 取出元素放入到arr
                    arr[index++] = bucket[k][l] ;
                }

            }
        }
        System.out.println("第2轮，对百位数的排序处理 arr = " + Arrays.toString(arr));*/

        /**
         * 关于如何取 整数 中的 个数 十位数 和 百位数
         *  通式： 注：计算顺序 ： 乘除 > 加减 > 取模
         *      取出个位： (n / 1) % 10
         *      取出十位： (n / 10) % 10
         *      取出百位： (n / 100) % 10
         *  这个规律看上去像不像下面的 getNextNumber()方法里面的 操作
         */
    }
}

